package org.getOffer.offer32_3;

import java.util.*;

/**
 * @Author yu
 * @Date 2021/10/7
 */
public class Solution {

    public static void main(String[] args) {

        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);

        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;

        Solution solution = new Solution();

        List<List<Integer>> lists = solution.levelOrder(treeNode1);

        for (List<Integer> list : lists) {
            for (Integer i : list) {
                System.out.print(i);
            }
            System.out.println();
        }


    }

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        this.recursive(root, 0);
        for(int i=1;i<res.size();i+=2){
            Collections.reverse(res.get(i));
        }
        return res;
    }

    public void recursive(TreeNode root, Integer flag) {
        if (root == null) {
            return;
        }

        if (res.size() <= flag) {
            res.add(new ArrayList<>());
        }

        res.get(flag).add(root.val);

        this.recursive(root.left, flag+1);
        this.recursive(root.right, flag+1);

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}